package com.ljy.my_study.leetcode.完美矩形;

import com.ljy.my_study.util.ArrayUtil;
import sun.awt.image.IntegerComponentRaster;

import java.util.HashSet;
import java.util.Set;

/**
 * @author lijunying
 * @date 2021/11/16 8:57
 */
public class TestMain {

//    给你一个数组 rectangles ，其中 rectangles[i] = [xi, yi, ai, bi] 表示一个坐标轴平行的矩形。这个矩形的左下顶点是 (xi, yi) ，右上顶点是 (ai, bi) 。
//
//    如果所有矩形一起精确覆盖了某个矩形区域，则返回 true ；否则，返回 false 。
//
//             
//    示例 1：
//
//
//    输入：rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
//    输出：true
//    解释：5 个矩形一起可以精确地覆盖一个矩形区域。
//    示例 2：
//
//
//    输入：rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
//    输出：false
//    解释：两个矩形之间有间隔，无法覆盖成一个矩形。
//    示例 3：
//
//
//    输入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[3,2,4,4]]
//    输出：false
//    解释：图形顶端留有空缺，无法覆盖成一个矩形。
//    示例 4：
//
//
//    输入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
//    输出：false
//    解释：因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。
//             
//
//    提示：
//
//            1 <= rectangles.length <= 2 * 104
//    rectangles[i].length == 4
//            -105 <= xi, yi, ai, bi <= 105
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/perfect-rectangle
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

//    使用hash 记录每个矩形中含那些部分。会超时
    public static void main(String[] args) {
        int[][] rectangles= ArrayUtil.changeStr2Array("[[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]");
        System.out.println(new TestMain().isRectangleCover(rectangles));
        rectangles= ArrayUtil.changeStr2Array("[[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]");
        System.out.println(new TestMain().isRectangleCover(rectangles));
        rectangles= ArrayUtil.changeStr2Array("[[0,0,1,1],[0,1,3,2],[1,0,2,2]]");
        System.out.println(new TestMain().isRectangleCover(rectangles));
        rectangles= ArrayUtil.changeStr2Array("[[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]");
        System.out.println(new TestMain().isRectangleCover(rectangles));
    }

    public boolean isRectangleCover(int[][] rectangles) {
        int[] maxR={Integer.MAX_VALUE, Integer.MAX_VALUE,Integer.MIN_VALUE,Integer.MIN_VALUE};
        long size=0;
        Set<String> set=new HashSet<>();
        for(int i=0;i<rectangles.length;i++){
            int[] r=rectangles[i];
            size+=(r[2]-r[0])*(r[3]-r[1]);
            maxR[0]=Math.min(maxR[0],r[0]);
            maxR[1]=Math.min(maxR[1],r[1]);
            maxR[2]=Math.max(maxR[2],r[2]);
            maxR[3]=Math.max(maxR[3],r[3]);

            if(!appendPoint(set,r)){
                return false;
            }
        }
        long maxSize=(maxR[2]-maxR[0])*(maxR[3]-maxR[1]);
        return maxSize==size;
    }

    private boolean appendPoint(Set<String> set, int[] r){
        for(int i=r[0];i<r[2];i++){
            for(int j=r[1];j<r[3];j++){
                String s=""+i+"-"+j;
                if(set.contains(s)){
                    return false;
                }
                set.add(s);
            }
        }
        return true;
    }
}
